/**
 * 124. 二叉树中的最大路径和
 * https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/
 */
public class Solutions_124 {
    public static void main(String[] args) {
//        TreeNode root = new TreeNode(1);
//        root.left = new TreeNode(2);
//        root.right = new TreeNode(3);  // output: 6  {1 + 2 + 3}

        TreeNode root = new TreeNode(-10);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);  // output: 42  {15 + 20 + 7}

        int result = maxPathSum(root);
        System.out.println(result);
    }

    private static int res = Integer.MIN_VALUE;

    /**
     * 关键思路：
     * 对于每一个节点，最大路径和只可能存在两种情况：
     *      1. 左右子树 + 当前节点，可能是最大路径
     *      2. 左右子树中路径和较大的一条 + 当前节点的路径，返回给父节点（如果有），可能是最大路径
     * 对于遍历的节点，如果左右子树返回的是负数，那么就不取子树路径
     *      因为负数会减小路径和
     */
    public static int maxPathSum(TreeNode root) {
        getMax(root);
        return res;
    }

    public static int getMax(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftRes = Math.max(0, getMax(root.left));
        int rightRes = Math.max(0, getMax(root.right));
        // 最大路径和可能之一：左右子树 + 当前节点，组成最大值路径
        res = Math.max(res, root.val + leftRes + rightRes);
        // 最大路径和可能之一：左右子树中路径和较大的一方与当前节点组成路径，返回父节点
        return Math.max(leftRes, rightRes) + root.val;
    }
}
